import numpy as np
import random as rd
import drawNet as dn
def Price(m0, n, a, m):#Price有向网络模型构造算法，m0个初始节点，最终n个节点，常数a，每次新节点连边数m
    G = np.empty((n, n))
    deg = np.zeros((n))#入度
    for i in range(m0, n):
        cnt = 0
        prep = vis = np.zeros((n))
        p = deg 
        sump = np.sum(p)
        p = p + a
        p = p / (sump + a * i)#累计优势
        prep[0] = 0
        for j in range(1, n):
            prep[i] = prep[i - 1] + p[i]
        while(cnt < m):#连m条边
            r = rd.random()
            for j in range(1, n):
                if(r > prep[j]):
                    if(vis[j - 1] == 0):
                        G[i][j - 1] = 1
                        vis[j - 1] = 1
                        cnt += 1
                        break
        for j in range(0, i):#更新入度
            deg[j] += vis[j]
    return G
def Big_Price(m0, n, p, m):#n足够大时的Price有向网络模型构造算法
    G = np.empty((n, n))
    arr = []#array数组
    for i in range(1, m0):
        G[i - 1][i] = G[i][i - 1] = 1
        arr.append(i - 1)
        arr.append(i)
    lst = [j for j in range(0, m0)]
    for i in range(m0, n):
        cnt = 0
        tmp_arr = arr.copy()
        tmp_lst = lst.copy()
        while(cnt < m):#连m条边
            cnt += 1
            r = rd.random()
            #print(tmp_lst, lst)
            #print(cnt, len(tmp_lst))
            if(r < p): rp = rd.choice(tmp_arr)
            else: rp = rd.choice(tmp_lst)
            arr.append(rp)
            G[i][rp] = 1
            cnt_rp = tmp_arr.count(rp)
            for j in range(0, cnt_rp):
                tmp_arr.remove(rp)
            tmp_lst.remove(rp)
        lst.append(i)
    return G
dn.drawDiGraph(Price(3, 10, 2, 2))
dn.drawDiGraph(Big_Price(3, 100, 0.5, 3))